﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Maps;
using Algoritmia.DataStructures.Trees;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Matrix
{
    public class OptimalMatrixProductFinder
    {
        private readonly Func<int,IMap<Tuple<int, int>, int>> _createMap;

        public class ParenthesisTree : BinaryTree
        {
            private readonly int _index;

            public ParenthesisTree(int index)
            {
                _index = index;
                IsLeaf = true;
            }

            public ParenthesisTree(ParenthesisTree LHS, ParenthesisTree RHS)
                : base(null,LHS,RHS)
            {
                IsLeaf = false;
            }

            public bool IsLeaf { get; private set; }

            public int Value
            {
                get { return _index; }
            }

            public override string ToString()
            {
                if (IsLeaf)
                {
                    return _index.ToString();
                }
                else
                {
                    return "[" + Left + ", " + Right + "]";
                }
            }
        }
        
        public OptimalMatrixProductFinder(Func<int,IMap<Tuple<int,int>,int>> createMap = null)
        {
            _createMap = createMap ?? (n => AlgoritmiaFactory.Maps<Tuple<int, int>, int>.Default);
        }

        public int Flops(IList<Tuple<int,int>> dimensions)
        {
            int n = dimensions.Count;
            var P = _createMap(n);
            for(int i = 0; i < n; i++)
            {
                P[new Tuple<int, int>(i, i)] = 0;
            }
            for (int k = 1; k < n; k++)
            {
                for (int i = 0; i < n - k; i++)
                {
                    P[new Tuple<int, int>(i, i + k)] =
                        Enumerable.Range(i, k).Select(
                            j =>
                            P[new Tuple<int, int>(i, j)] + dimensions[i].Item1 * dimensions[j].Item2 * dimensions[i + k].Item2 +
                            P[new Tuple<int, int>(j + 1, i+k)]).Min();
                }
            }
            return P[new Tuple<int, int>(0, n - 1)];
        }

        public ParenthesisTree Parenthesized(IList<Tuple<int, int>> dimensions)
        {
            int n = dimensions.Count;
            var P = _createMap(n);
            var back = _createMap(n);
            for (int i = 0; i < n; i++)
            {
                var tple = new Tuple<int, int>(i, i);
                P[tple] = 0;
                back[tple] = -1;
            }
            for (int k = 1; k < n; k++)
            {
                for (int i = 0; i < n - k; i++)
                {
                    var tple = new Tuple<int, int>(i, i + k);
                    var result =
                        Enumerable.Range(i, k).Select(
                            j => new
                                     {
                                         Flops =
                                     P[new Tuple<int, int>(i, j)] +
                                     dimensions[i].Item1*dimensions[j].Item2*dimensions[i + k].Item2 +
                                     P[new Tuple<int, int>(j + 1, i + k)]
                                         ,
                                         Index = j
                                     }
                            ).ArgMin(e => e.Flops);
                    P[tple] = result.Flops;
                    back[tple] = result.Index;
                }
            }

            Func<int, int,ParenthesisTree> backtrace = null;
            backtrace = (i, k) =>
                            {
                                var j = back[new Tuple<int, int>(i, k)];
                                if (j == -1)
                                {
                                    return new ParenthesisTree(i);
                                }
                                else
                                {
                                    var left = backtrace(i, j);
                                    var right = backtrace(j + 1, k);
                                    return new ParenthesisTree(left, right);
                                }
                            };
            return backtrace(0, n - 1);
        }
    }
}
